# 1线性查找 linear reach
# def linear_reach(list,value):#输入一个列表和一个要找的值
#     for ind,val in enumerate(list):
#         if value==val:
#             return ind
#         else:
#             return None
# enumerate(list)可带下标遍历 index 为遍历的下标 val 为此列表的值
# 一旦传入的值和列表的值一样 返回下标 如果遍历完都找不到  返回None
# 时间复杂度为  O（n）

##----------------------------------------------------------

# 2 二分查找 binary reach
# def binary_reach(list,num):
#     left=0
#     right=len(list)-1
#     while left<=right:
#         mid = (left + right) // 2
#         if list[mid]<num:
#             left=mid+1
#         elif list[mid]>num:
#             right=mid-1
#         else:
#             return mid
#     else:
#         return None

# 不断找出中间值并与之比较进而减少复杂程度和遍历个数
# （或者说 在二分中不存在遍历，如果数据较大二分相对于线性查找可以优化很多）
# 时间复杂度为   O（logn）


# 二分查找和线性查找总结
# 二分查找比线性查找时间复杂度低得多 但是
# 线性查找对列表无要求（不过大超内存）
# 但是二分查找需要列表是有序的 从小到大（注意特殊情况存在两个num，返回下标小的）


# ----------------------------------------------------------

# 常见排序算法
# 冒泡排序，选择排序 插入排序 快速排序 堆排序 归并排序 希尔排序 记数排序 基数排序


# 3.冒泡排序
# 列表每两个相邻的数，如果前面的比后面的大 就交换位置
# 一趟排序后 无序区减少一个数 有序区增加一个数
# 代码关键 几次排序 （几趟） 无序区范围
# 列表生成式 a=[exp for iter_var in iterable]

# def bubble_sort(list):
#     for i in range(len(list)-1):
#         flag=True
#         for j in range(len(list)-1-i):
#             if list[j]>list[j+1]:
#                 list[j],list[j+1]=list[j+1],list[j]
#                 flag=False
#         if flag:
#             return list
#
# a=[1,2,8,6,9,5,4]
# bubble_sort(a)
# 两处循环 称为外循环内循环 每次外循环时 就是说每一趟 把flag定义为true
# 在内循环执行后 把flag变为false 如果某一趟 flag不再变化
# （if 默认接收到的是ture ）
# 则证明不需要再交换可以退出了
# ------------------------------------------------

# 4.选择排序
# def select_sort(li):
#     for i in range(len(li)-1):
#         min=i
#         for j in range(i+1,len(li)):
#             if li[j]<li[min]:
#                 min=j
#         if min!=i:
#             li[i],li[min]=li[min],li[i]
#
# a=[9,5,6,7,3,1,4]
# select_sort(a)
# print(a)
# 通过不断把最小数放到最前面 把排序过的数的叫有序区 没排序的叫无序区
# 是通过对无序区位置的交换来优化代码


# ----------------------------------------------------------

# 插入排序
# def insert_sort(list):
#     for i in range(1,len(list)):
#         tmp=list[i]
#         j=i-1
#         while j>=0 and list[j]>tmp:
#             list[j+1]=list[j]
#             j-=1
#         list[j+1]=tmp
# a=[9,3,6,5,7,4,1,2,1,0]
# insert_sort(a)
# print(a)


# -------------------------------


# 简单排序总结
# 插入选择冒泡排序都是简单排序 原地排序（不需要创建新列表）
# 时间复杂度都是O（n方）  容易超时
# 像10000个元素的乱序列表 冒泡排序需要十多秒


# -------------------------------

# 较复杂排序
# 快速排序
# 快排有两个函数组成 一个是partition 一个是快排 其中partition函数为核心
# 快排主要是找到中间值 然后左边的都比中间值大 右边的都比中间值小
# 然后再具体对中间值左右进行排序 如果只有一个或者没有数比这个数大 则排序完成
# def partition(list,left,right):
#     tmp=list[left]#如果是对整个列表排序 可以用0开始 但有时可能只对列表部分排序
#     #所以最初值用list[left]
#     while left<right:
#         while left<right and list[right]>=tmp:
#             right-=1
#         list[left]=list[right]
#         while left<right and  list[left]<=tmp:
#             left+=1
#         list[right]=list[left]
#     list[right]=tmp
#     return right
#
# 当代码执行完毕 left和right重合 则确定中间值tmp和下标partition最后两行right和left值是一样的
# 在快排函数中把中间值返回 赋值给mid
#
# def quick_sort(list,left,right):
#     if left<right:
# #需要排序的至少有两个元素 如果某一个数前只有一个数或者没有 说明这两个或者说一个排序完成
#         mid=partition(list,left,right)
#         quick_sort(list,left,mid-1)
#         quick_sort(list,mid+1,right)
# a=[6,8,2,4,8,4,9,5,5,7,2,1,5]
# quick_sort(a,0,len(a)-1)
# print(a)


# 快排最优时间复杂度为O（nlogn）
# 最坏情况 如果数组[9,8,7,6,5,4,3,2,1]则需要特别多时间 这种特殊情况复杂度不再是O（nlogn）
# 快排时间复杂度不稳定但是相对来说很快 比简单排序速度快


# -----------------------------------------------


# 堆排序 树
# 基本概念：
# 节点的度：             一个节点含有的子树的个数称为该节点的度； 如上图：A的为6（A分了六个叉）
# 叶节点或终端节点：       度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点（不再分叉的地方）
# 非终端节点或分支节点：    度不为0的节点； 如上图：D、E、F、G…等节点为分支节点（有分叉的地方）
# 双亲节点或父节点：       若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
# （如A分出B则A为B 的父节点B为A的子节点或称之为孩子节点）
# 孩子节点或子节点：       一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
# 兄弟节点：             具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
# 如A分出BCD则BCD 互相为兄弟节点 他们有同一个父节点
# 树的度：              一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
# A分了6个子节点 分支最多 所以度是6
# 节点的层次：           从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
# 树的高度或深度：        树中节点的最大层次； 如上图：树的高度为4
# 堂兄弟节点：           双亲在同一层的节点互为堂兄弟；如上图：H、I互为堂兄弟节点
# 节点的祖先：           从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
# 子孙：                以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
# 森林：                由m（m>=0）棵互不相交的树的集合称为森林；

# 树的表示方式常见的有三种:
# 1双亲表示法
# 2孩子表示法
# 3孩子兄弟表示法
# ---------------------------------------

# 二叉树

# 二叉树的基本概念以及特性
# 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树
# 的二叉树组成。

#  二叉树的特点：
# 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
# 二叉树的子树有左右之分，其子树的次序不能颠倒。

# 二叉树种类

# 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
# 说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

# 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K
# 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对
# 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
# 其中叶节点只能出现在最下层和次下层 并且最下面一层的节点都集中 再该层最左边的若干位位置的二叉树
# 相当于完全二叉树最后几个被拿掉了

# 二叉树节点数量 从上到下 第几层就有 2的 n-1 次方个

# 二叉树一般可以使用两种结构存储，
# 一种顺序结构
# 一种链式结构。

# 顺序存储：
# 顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。
# 而现实中使用中只有堆才会使用数组来存储,二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。


# 节点和下标关系
# 假设一棵二叉树 用列表存储 按顺序从上到下从左到右
# 父节点下标为i
# 其中父节点和左孩子节点下标关系 为：i >> 2i+1
# 其中父节点和右孩子节点下标关系为 ：i >>2i+2
# 孩子节点-1整除2  （//）就是父节点


# ----------------------------------------------------------------------------

# 堆排序
# 堆：一种特殊的完全二叉树结构
# 大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大

# 小根堆：一棵完全二叉树，满足任一节点都比其它孩子节点小

# 假设根节点的左右子树都是堆，但根节点不满足堆的性质
# 可以通过一次向下调整来将其变成一个堆

# # 堆排序过程
# # 1建立堆
# # 2得到堆顶元素为最大元素
# # 3去掉堆顶，将堆最后一个元素放到堆顶（否则就不是完全二叉树了），此时可通过
# # 一次调整重新使堆有序。
# # 4堆顶元素为第二大元素
# # 5重复步骤三直到堆变空
# def sift(list, low, high):  # 调整
#     """
#
#     :param list:传入的列表
#     :param low: 堆根节点
#     :param height:堆最后一个元素
#     :return:
#     """
#     i = low  # 指向根节点
#     j = 2 * i + 1  # j最开始为左孩子
#     tmp=list[low]#tmp存入堆顶元素
#     while j<=high:
#         if j+1<=high and list[j+1]>list[j]:
#             j=j+1 #j指向左孩子
#         if list[j]>tmp:
#             list[i]=list[j]
#             i=j#i向下挪一个位置
#             j=2*i+1#  j向下挪一个位置
#         else: #list[j]<tmp
#             list[i]=tmp
#             break
#     else:
#             list[i]=tmp
#
#
# def heap_sort(list):
#     n=len(list)
#     for i in range((n-2)//2,-1,-1):
#         #i表示建堆的时候表示的部分的根的下标
#         sift(list,i,n-1)#建堆完成
#
#     for i in range(n-1,-1,-1):
#         #i指向当前堆最后一个元素
#         list[0],list[i]=list[i],list[0]
#         sift(list,0,i-1)#i-1是新的high
#
# a=[8,5,7,4,3,1,8,6,5]
# heap_sort(a)
# 堆排序时间复杂度为 O（nlogn)和快排时间复杂度一样 但是快排比堆排快

# #实际上在python中 有模块可以实现堆排序
# import heapq
# import random
# a=list(range(50))
# random.shuffle(a)
#
# heapq.heapify(a)#实现建堆 不过是小根堆 最上面根的最数最小
#
# heapq.heappop(a)#每次返回一个列表最小值
# print(heapq.heappop(a))
# ---------------------------------------------------------


# 堆排序实际应用 topk问题
# 如果要取列表前k大的数用
# 堆排序 O(klogn)
# 简单排序 O(kn)
# 排序后切片 O(nlogn)
# 代码
# def sift(list, low, high):  # 调整
#     """
#
#     :param list:传入的列表
#     :param low: 堆根节点
#     :param height:堆最后一个元素
#     :return:
#     """
#     i = low  # 指向根节点
#     j = 2 * i + 1  # j最开始为左孩子
#     tmp=list[low]#tmp存入堆顶元素
#     while j<=high:
#         if j+1<=high and list[j+1]>list[j]:
#             j=j+1 #j指向左孩子
#         if list[j]>tmp:
#             list[i]=list[j]
#             i=j#i向下挪一个位置
#             j=2*i+1#  j向下挪一个位置
#         else: #list[j]<tmp
#             list[i]=tmp
#             break
#     else:
#             list[i]=tmp
#
#
# def topk(list,k):
#     heap=list[0:k]
#     for i in range((k-2)//2,-1,-1):
#         sift(heap,i,k-1)
#         #建堆
#     for i in range(k,len(list)-1):
#         if list[i]>heap[0]:
#             heap[0]=list[i]
#             sift(heap,0,k-1)
#         #遍历
#     for i in range(k-1,-1,-1):
#         heap[0],heap[i]=heap[i],heap[0]
#         sift(heap,0,i-1)
#         #出数
#     return heap


# ---------------------------------------------------------


# 归并排序的归并
# 1分解 把列表越分越小，直至分成一个元素
# 2终止条件：一个元素是有序的
# 3合并：将两个有序列表归并，列表越来越大
# 归并排序时间复杂度
# 时间 O(nlogn)
# 空间 O(n)
# 代码如下
# def merge(li,low,mid,high):
#     i=low
#     j=mid+1
#     ltmp=[]
#     while i<=mid and j<=high:#两个列表左右两边都有数
#         if li[i]<li[j]:
#             ltmp.append(li[i])
#             i+=1
#         else:
#             ltmp.append(li[j])
#             j+=1
#     #当跳出while循环 肯定有一个列表空了
#     while i<=mid:
#         ltmp.append(li[i])
#         i+=1
#     while j<=high:
#         ltmp.append(li[j])
#         j+=1
#     li[low:high+1]=ltmp
#
# a=[6,7,8,9,1,2,3,4]
#
# merge(a,0,3,7)
# 使用要求 mid为第一个有序（从小到大）列表最后一个的下标，high为第二个列表的最后一个下标
# 两个列表都要有序才能使用


# #归并排序实现
# def merge(li,low,mid,high):
#     i=low
#     j=mid+1
#     ltmp=[]
#     while i<=mid and j<=high:#两个列表左右两边都有数
#         if li[i]<li[j]:
#             ltmp.append(li[i])
#             i+=1
#         else:
#             ltmp.append(li[j])
#             j+=1
#     #当跳出while循环 肯定有一个列表空了
#     while i<=mid:
#         ltmp.append(li[i])
#         i+=1
#     while j<=high:
#         ltmp.append(li[j])
#         j+=1
#     li[low:high+1]=ltmp
#
#
# def merge_sort(li,low,high):
#     if low<high:#至少两个元素，递归
#         mid=(low+high)//2
#         merge_sort(li,low,mid)
#         merge_sort(li,mid+1,high)
#         merge(li,low,mid,high)
#
# a=[8,7,5,2,1,5,4,4,6,41]


# # 希尔排序
# def insert_sort_gap(li, gap):
#     for i in range(gap, len(li)):
#         tmp = li[i]
#         j = i - gap
#         while j >= 0 and li[j] > tmp:
#             li[j + gap] = li[j]
#             j -= gap
#         li[j + gap] = tmp
#
#
# def shell_sort(li):
#     d = len(li) // 2
#     while d >= 1:
#         insert_sort_gap(li, d)
#         d //= 2
# #测试：通过
# a= list(range(1000))
# import random
# random.shuffle(a)
# shell_sort(a)
# print(a)


# # 计数排序,假设有100个数字 但是不知道列表长度
# #时间复杂度  O(n)
# #空间复杂度
# def count_sort(li, max_count=100):
#     count = [0 for _ in range(max_count + 1)]
#     for val in li:
#         count[val] += 1
#     li.clear()
#     for ind, val in enumerate(count):
#         for i in range(val):
#             li.append(ind)
#
#
# import random
#
# li = [random.randint(0, 100) for _ in range(1000)]
# print(li)
# count_sort(li)
# print(li)


# #桶排序 首先将元素放在不同桶中，在对每个桶中元素排序
# 桶排序表现取决于数据的分布。也就是需要对不同数据排序时采取不同的分桶策略
# 数据分布越平均速度越快
# 平均情况时间复杂度 O(n+k)
# 最坏情况时间复杂度 O((n**2)*k)
# 空间复杂度   O(nk)
# def bucket_sort(li,n=100,max_num=10000):
#     buckets=[[] for _ in range(n)]
#     for var in li:
#         i = min(var//(max_num//n),n-1)
#         buckets[i].append(var)
#         for j in range(len(buckets[i])-1,0,-1):
#             if buckets[i][j]<buckets[i][j-1]:
#                 buckets[i][j],buckets[i][j-1]=buckets[i][j-1],buckets[i][j]
#             else:
#                 break
#     sorted_li=[]
#     for buc in buckets:
#         sorted_li.extend(buc)
#     return sorted_li
#
# import random
#
# li = [random.randint(0, 10000) for _ in range(100000)]
# print(li)
# li=bucket_sort(li)
# print(li)


# 基数排序（多关键字排序）
# 时间复杂度 O(kn)
# 空间复杂度 O(k+n)
# k表示数字位数
# def radix_sort(li):
#     max_num=max(li)#求出最大值
#     it=0
#     while 10**it <=max_num:
#         buckets=[[]for _ in range(10)]
#         for var in li:
#             digit=(var//10**it)%10
#             buckets[digit].append(var)
#             #分桶完成
#         li.clear()
#         for buc in buckets:
#                 li.extend(buc)
#             #把数重新写回li
#         it += 1
#
# import random
# li = list(range(1000))
# random.shuffle(li)
# radix_sort(li)
# print(li)

# -----------------------------------------------------------------------
# 数据结构
# 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成
# 数据结构就是设计数据以何种方式组织并存储在计算机中
# 列表集合等都是一种数据结构
# 程序=数据结构+算法
# 数据结构按照其逻辑结构可分为 线性结构 树结构 图结构
# 线性结构：数据结构中的元素存在一对一的相互关系
# 树结构：数据结构中的元素存在一对多的相互关系
# 图结构：数据结构中的元素存在多对多的相互关系

# python中的列表相当于别的编程语言中的数组但是还有些不同
# 1.数组元素类型要相同 （要么都是字符串，要么都是数字）
# 2.数组长度固定 （别的语言在创建数组时就规定了数组的长度而python不一样）

# 与其他编程语言不同的是 python中的列表可以存储不同元素类型因为python中的列表存储的是地址
# 而别的编程语言存的就是元素
# python中删除和插入复杂度为O(n)


# -----------------------------------------------------------------------
# 栈的介绍
# 栈是一个数据集合，可以理解为只能在一端进行插入或者删除操作列表
# 栈的特点 后进先出（LIFO)(last-in，first-out）
# 栈的概念：栈顶，栈底
# 栈的基本操作： 进栈（压栈）：push
# 出栈：pop
# 取栈顶：gettop 只查找栈顶但不操作

# 使用一般列表结构即可实现栈
# 进栈：li.append
# 出栈：li.pop
# 取栈顶：li[-1]

# 栈的经典问题 括号匹配

# 重点！！！！！！
# 栈和队列应用之 迷宫问题
# 栈 深度优先搜索
# 回溯法
# #用栈可以解决迷宫问题 但是仅仅是解决 不一定是最短路径
# 思路 从一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其它方向的点
# 使用栈存储当前路径

# # example：
# maze= [
#     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
#     [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
#     [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
#     [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
#     [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
#     [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
#     [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
#     [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
#     [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
#     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# ]
# # direction 方向 分别代表右，左，下，上（看作平面直角坐标系 左上角1，1，终点为8，8，可以看作向右为x正半轴，向下为y正半轴）
# dirs = [
#     lambda x, y: (x + 1, y),
#     lambda x, y: (x - 1, y),
#     lambda x, y: (x, y + 1),
#     lambda x, y: (x, y - 1),
# ]

#
# # path 道路 轨道
# def maze_path(x1, y1, x2, y2):
#     stack = []  # 建立一个空栈
#     stack.append((x1, y1))  # 将起点放入栈
#     while (len(stack)) > 0:
#         # current 现在的 node 节点（可数名词复数加s）
#         curnode = stack[-1]  # 拿到现在的节点
#         if curnode[0] == x2 and curnode[1] == y2:  # 判断现在节点是否和终点重合，若条件成立则到达终点
#             for i in stack:
#                 print(i)
#             return True
#         # 下面这个循环是为了移动
#         for dir in dirs:
#             nextnode = dir(curnode[0], curnode[1])  # 此处相当于调用匿名函数进行移动 而括号里的是传入的参数代表x，y
#             # 如果下一个节点能走
#             if maze[nextnode[0]][nextnode[1]] == 0:  # 此处是查找迷宫里这个节点的值是否为0
#                 stack.append(nextnode)  # 条件成立则加入栈中
#                 maze[nextnode[0]][nextnode[1]] = 2  # 并标记这个走过的点为2 证明走过了
#                 break  # 此处break表示走了一个方向以后就结束开始从这个点再找别的方向
#         else:  # 此处else和上面和for构成for else语句 当这个节点上下左右都不能走 不执行break 则进入else循环
#             # 代表这个点 （也就是上面的nextnode）走不了但是通过else标记走过了（标记为2）
#             maze[nextnode[0]][nextnode[1]] = 2
#             stack.pop()  # 此处代表退 把这个nextnode删了  栈是后进先出 所以因为刚加过nextnode所以pop删除的也是nextnode
#     else:  # 此else和while对应 当栈空了但是没有走到终点证明是无解 所以返回false
#         print("没有路")
#         return False
#
#
# maze_path(1, 1, 8, 8)


# -----------------------------------------------------------------------

# 队列queue 是一个数据集合仅允许在列表的一端进行插入在另一端进行删除
# 进行插入的一端称为队尾（rear），插入动作称为进队或入队
# 进行删除的一端称为队头（front），删除动作称为出队
# 队列的性质：FIFO 先进先出（first-in first-out)

# 队列的实现方式 环形队列
# 环形队列当队尾指针     front==maxsize-1时再前进一个位置就自动到0
# 队首指针前进1         front=（front+1）%maxsize
# 队尾指针前进1         rear=(rear+1)%maxsize
# 队空条件             front=rear
# 队满条件            （rear+1）%maxsize==front

# 双向队列
# 基本操作：
# 队首进队
# 队首出队
# 队尾进队
# 队尾出队

# python队列内置模块
# 使用方法 from collections import deque
# 创建队列 queue=deque（）
# 进队append（）
# 出队popleft（）
# 双向队列队首进队 appendleft（）
# 双向队列队尾出队 pop（）

# 利用队列可以读取文件后几行因为队列如果超出规定长度会自动把队首舍去
# 所以可以用这个特性读取后几行 如果读前几行循环即可

# 队列解决迷宫问题
# 广度优先搜索
# 思路：从一个节点开始，寻找所有接下来能继续走的点，继续不断寻找，直到找到出口。
# 使用队列存储当前正在考虑的节点

# #example
# from collections import deque
# #
# maze= [
#     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
#     [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
#     [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
#     [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
#     [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
#     [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
#     [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
#     [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
#     [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
#     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# ]
# # direction 方向 分别代表右，左，下，上（看作平面直角坐标系 左上角1，1，终点为8，8，可以看作向右为x正半轴，向下为y正半轴）
# dirs = [
#     lambda x, y: (x + 1, y),
#     lambda x, y: (x - 1, y),
#     lambda x, y: (x, y + 1),
#     lambda x, y: (x, y - 1),
# ]
#
# def print_r(path):
#     curnode=path[-1]
#     realpath=[]
#     while curnode[2]!=-1:
#         realpath.append(curnode[0:2])
#         curnode = path[curnode[2]]
#
#     realpath.append(curnode[0:2])#这是为了把起点也加进去
#     realpath.reverse()#对原来列表进行倒序排序（直接改变原列表）
#     for i in realpath:
#         print(i)
#
# def maze_path_queue(x1,y1,x2,y2):
#     queue=deque() #创建队列
#     queue.append((x1,y1,-1))#三个参数 是为位置和出发点下标 起点无出发点所有下标写-1
#     path=[]
#     while len(queue)>0:
#         curnode=queue.pop()#拿到当前坐标
#         path.append(curnode)
#         if curnode[0]==x2 and curnode[1]==y2:#证明到达终点
#             print_r(path)
#             return True
#         for dir in dirs:
#             nextnode=dir(curnode[0],curnode[1])
#             if maze[nextnode[0]][nextnode[1]]==0:
#                 queue.append((curnode[0],curnode[1],len(path)-1))#后续节点进队 并记录哪个点带他来的
#                 maze[nextnode[0]][nextnode[1]]=2#标记走过了
#                 #这里最后不需要break因为队就是查找所有可能性
#     else:
#         print("没有路")
#         return False
# maze_path_queue(1, 1, 8, 8)

# 队列中存在多个点 所以通过下标寻找第一个到达终点的原最短路径


# -----------------------------------------------------------------------

# 链表
# 链表是由一系列节点组成的元素集合。每个节点包含两部分，数据域item和指向下一个节点的指针next
# 通过节点之间的相互连接最终串联成一个链表
# 创建链表
# 头插法：从头插入让新插入的元素变成头
# 尾插法：从尾插入 让新插入的元素变成尾


# class Node:
#     def __init__(self,item):
#         self.item=item
#         self.next=None
#
# def create_liknlist_head(li):#头插法 头插法只需要知道头
#     head= Node(li[0])#列表第一个元素当作头
#     for i in li[1:]:
#         node=Node(i)
#         node.next=head
#         head=node
#     return head
#
# def create_linklist_tail(li):#尾插法需要知道头和尾
#     head=Node(li[0])
#     tail=head
#     for I in li[1:]:
#         node=Node[I]
#         tail.next=node
#         tail=node
#     return head
#
#
#
# def print_linklist(lk):#这个函数用来打印整个链表
#     while lk:
#         print(lk.item,end=',')
#         lk=lk.next


# 链表节点的插入和删除

# p.next=curNode.next
# curnNode.next=p


# 双链表
# 双链表的每个节点有两个指针：一个指向后一个节点，另一个指向前一个节点。
# 双链表节点的插入
# p.next=curNode.next
# curNode.next.prior=p
# p.prior=curNode
# curNode.next=p

# 双链表节点的删除
# p=curNode.next
# curNode.next=p.next
# p.next.prior=curNode
# del p

# 链表复杂度分析
# 顺序表（列表/数组）与链表
# 按元素值查找
# 按下标查找
# 在某元素后插入
# 删除某元素


# -----------------------------------------------------------------------

# 哈希表也称散列表 是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。
# 哈希函数h(k)将元素关键字k作为自变量，返回元素的存储下标

# 由于哈希表的大小是有限的，而要存储的值的总数量是无限的，因此对于任何哈希函数，都会出现
# 两个不同元素映射到同一位置上的情况，这种情况叫做哈希冲突
# 比如h(k)=k%7,  h(0)=h(7)=h(14)=...

# 解决哈希冲突 开放寻址法

# 开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值
# 线性探查：如果位置i被占用 则探查i+1，i+2....
# 二次探查：如果位置i被占用，则探查  i+(1**2),i-(1**2),i+(2**2),i-(2**2).....
# 二度哈希有n个哈希函数，当使用第一个哈希函数h1发生冲突时，则尝试使用h2，h3

# 解决哈希冲突 拉链法
# 拉链法:哈希表每个位置都连接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后。

# 哈希表——常见哈希函数
# 除法哈希法h(k)=k%m
# 乘法哈希法：h(k)=floor(m*(A*key%1))
# 全域哈希法：ha,b(k)=((a*key+b)% p)mod m a,b=1,2...p-1  mod意思是取余 相当于%

# 通过一个哈希函数来计算数据存储位置的数据结构，通常支持如下操作
# insert(key,value):插入键值对(key,value)
# get(key):如果存在键为key的键值对则返回其value否则返回空值
# delet(key): 删除键为key的键值对

# 直接寻址表：当关键字的全域比较小时，直接寻址是一种简单而有效的办法
# 缺点：当域U很大时，需要消耗大量内存，很不实际
# 如果域U很大而实际出现的key很少，则大量空间被浪费
# 无法处理关键字不是数字的情况
#
# 直接寻址表：key为k的元素放到k位置上
# 改进直接寻址表：哈希(hashing)
# 构建大小为m的寻址表T
# key为k的元素放到h(k)位置上
# h(k)是一个函数，其将域U映射到表T[0,1···,m-1]


# 哈希表的应用——集合与字典
# 字典和集合都是通过 哈希表实现的
# 使用哈希表存储字典，通过哈希函数将字典的键映射为下标
# 如果发生哈希冲突则通过拉链法或开放寻址法解决

# 哈希表的应用 md5
#  应用举例文件的哈希值
#  算出文件的哈希值，若两个文件哈希值相同，则可认为这两个文件是相同的因此：
# 1用户可以利用它来验证下载的文件是否完整
# 2云存储服务商可以利用它来判断用户要上传的文件 是否已经存在于服务器上，从而实现妙传的功能，同时
# 避免存储过多相同的文件副本

# 哈希表的应用 SHA2算法


# -----------------------------------------------------------------------

# 树和二叉树
# 树是一种数据结构 比如 目录结构
# 树是一种可以递归定义的数据结构
# 树是由n个节点组成的集合
# 如果n=0，那这是一颗空树
# 如果n>0 那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树
# 一些概念：根节点 叶子节点
# 树的深度 （高度)
# 树的度
# 孩子节点/父节点
# 子树
#


# 链式存储：
# 二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
# 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，

# 左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
# 链式结构又分为二叉链和三叉链(红黑树)。

# 二叉树遍历方式：
# 前序遍历：EACBDGF
# 中序遍历：ABCDEFG
# 后序遍历：BDCAFGE
# 层次遍历：EAGCFBD

# 68
# #层次遍历引入库
# from collections import deque
# class BiTreeNode:
#     def __init__(self,data):
#         self.data =data
#         self.lchild = None #左孩子
#         self.rchild = None #右孩子
#
# a = BiTreeNode("A")
# b = BiTreeNode("B")
# c = BiTreeNode("C")
# d = BiTreeNode("D")
# e = BiTreeNode("E")
# f = BiTreeNode("F")
# g = BiTreeNode("G")
#
# e.lchild = a
# e.rchild = g
# a.rchild = c
# c.lchild = b
# c.rchild = d
# g.rchild = f
#
# root = e
#
# #前序遍历
# def pre_order(root):
#     if root:
#         print(root.data,end=",")
#         pre_order(root.lchild)
#         pre_order(root.rchild)
#
# #pre_order(root)
#
# #中序遍历
# def in_order(root):
#     if root:
#         in_order(root.lchild)
#         print(root.data,end=",")
#         in_order(root.rchild)
#
# #in_order(root)
#
# #后序遍历
# def post_order(root):
#     if root:
#         in_order(root.lchild)
#         in_order(root.rchild)
#         print(root.data, end=",")
#
# #post_order(root)
#
# #层次遍历
# def level_order(root):
#     queue= deque()
#     queue.append(root)
#     while len(queue) >0: #只要队不空
#         node=queue.popleft()
#         print(node.data,end=',')
#         if node.lchild:
#             queue.append(node.lchild)
#         if node.rchild:
#             queue.append(node.rchild)
#
# #level_order(root)


# 69
# 二叉搜索书是一颗二叉树且满足性质：设x是二叉树的一个节点。
# 如果y是x左子树的一个节点，那么y.key<=x.key
# 如果y是x右子树的一个节点，那么y.key>=x.key
# 也就是对于父节点来说左孩子节点一定自己小右孩子节点一定比自己大
# 二叉搜索树的操作：查询，插入，删除。


# 70-73
#
# class BiTreeNode:
#     def __init__(self, data):
#         self.data = data
#         self.lchild = None  # 左孩子
#         self.rchild = None  # 右孩子
#         self.parent = None  # 父节点
#
#
# class BST:
#     def __init__(self):
#         self.root = None
#
#     # 增
#     def insert(self, node, val):  # 带递归的增加
#         if not node:
#             node = BiTreeNode(val)
#         elif val < node.data:
#             node.lchild = self.insert(node.lchild, val)
#             node.lchild.parent = node
#         elif val > node.data:
#             node.rchild = self.insert(node.rchild, val)
#             node.rchild.parent = node
#         return node
#
#     def insert_no_rec(self, val):  # 不带递归的增加
#         p = self.root
#         if not p:
#             self.root = BiTreeNode(val)
#             return
#         while True:
#             if val < p.data:
#                 if p.lchild:
#                     p = p.lchild
#                 else:  # 左孩子不存在
#                     p.lchild = BiTreeNode(val)
#                     p.lchild.parent = p
#                     return
#             elif val > p.data:
#                 if p.rchild:
#                     p = p.rchild
#                 else:
#                     p.rchild = BiTreeNode
#                     p.rchild.parent = p
#                     return
#             else:
#                 return
#
#     # 查
#     def query(self, node, val):  # 带递归的查询
#         if not node:
#             return None
#         if node.data < val:
#             return self.query(node.rchild, val)
#         elif node.data > val:
#             return self.query(node.lchile, val)
#         else:
#             return node
#
#     def query_no_rec(self, val):  # 不带递归的查询
#         p = self.root
#         while p:
#             if p.data < val:
#                 p = p.rchild
#             elif p.data > val:
#                 p = p.lchild
#             else:
#                 return p
#         return None
#
#     # 如果要删除的节点是叶子节点：直接删除
#     # 如果要删除的节点只有一个孩子：将此节点的父亲与孩子连接。
#     # 然后删除该节点
#     # 如果要删除的节点有两个孩子：将其右子树的最小节点
#     # （该节点最多有一个右孩子）删除，并替换当前节点
#
#     # 删
#     def __remove_node_1(self, node):
#         # 情况1：node是叶子节点
#         if not node.parent:
#             self.root = None
#         if node == node.parent.lchild:
#             node.parent.lchild = None
#         else:
#             node.parent.rchild=None
#
#     def __remove_node_21(self,node):
#         #情况2.1：node有一个左孩子
#         if not node.parent: #根节点
#             self.root=node.lchild
#             node.lchild.parent=None
#         elif node==node.parent.lchild:
#             node.parent.lchild= node.lchild
#             node.lchild.parent=node.parent
#         else:
#             node.parent.rchild=node.lchild
#             node.lchild.parent=node.parent
#
#     def __remove_node_22(self,node):
#         #情况2.2：node只有一个右孩子
#         if not node.parent:
#             self.root=node.rchild
#         elif node== node.parent.lchild:
#             node.parent.lchild=node.rchild
#             node.rchild.parent=node.parent
#         else:
#             node.parent.rchild=node.rchild
#             node.rchild.parent=node.parent
#
#
#     def delete(self,val):
#         if self.root:#不是空树
#             node=self.query_no_rec()
#             if not node:#不存在
#                 return False
#             if not node.lchild and not node.rchild:
#                 self.__remove_node_1(node)
#             elif not node.rchild:
#                 self.__remove_node_21(node)
#             elif not node.lchild:
#                 self.__remove_node_22(node)
#             else:
#                 min_node=node.rchild
#                 while min_node.lchild:
#                     min_node=min_node.lchild
#                 node.data=min_node.data
#                 #删除min_node
#                 if min_node.rchild:
#                     self.__remove_node_22(min_node)
#                 else:
#                     self.__remove_node_1(min_node)
#
#
# tree=BST([1,4,2,5,3,8,6,9,7])
# tree.in_order(tree.root)
# tree.delete(4)
# tree.in_order(tree.root)


# 二叉搜索树的效率
# 平均：时间复杂度O(lgn)
# 最坏 二叉搜索树非常偏斜
# 解决方案 随机化插入 AVL树

# AVL树
# AVL树是一颗自平衡二叉搜索树
# AVL树具有以下性质

# 根的左右子树的高度之差的绝对值不能超过1
# 根的左右子树都是平衡二叉树

# 75
# AVL树插入
# 插入一个节点可能会破坏AVL树的平衡，可以通过旋转操作来进行修正。
# 插入一个节点后只有从插入节点到根节点的路径上的节点的平衡可能被改变。
# 我们需要找出第一个破坏了平衡条件的节点，称之为K，K的两颗子树高度差2
# 不平衡的出现可能有4种情况
# 1不平衡是由于K的左孩子的左子树插入导致的：右旋
# 2不平衡是由于对K的右孩子的右子树插入导致的：左旋
# 不平衡是由于对K的右孩子的左子树插入导致：右旋-左旋
# 不平衡是由于对K的左孩子的右子树插入导致：左旋-右旋

# 76-79 AVL树

# AVL树拓展 B树（B-Tree）
# B树是一颗自平衡的多路搜索树。常用于数据库索引


# 80算法进阶


# 贪心算法又称贪婪算法是指在对问题求解时总是做出在当前来看是最好的选择。也就是说，
# 不从整体最优上加以考虑，她所作出的是在某种意义上的局部最优解。

# 贪心算法并不保证会得到最优解，但是在某些问题上贪心算法的解就是最优解
# 要会判断一个问题能否用贪心算法计算。

# 找零问题
# 假设商店老板找零n元 钱币面额有 100 50 20 5 1
# 如何找零使得所需钱币数量最少

# t=[100,50,20,5,1]
#
# def change(t,n):
#     m=[0 for _ in range(len(t))]
#     for i,money in enumerate(t):
#         m[i]=n//money
#         n=n%money
#     return m,n
#
# print(change(t,376))

# 81
# 背包问题
# 一个小偷在某商店内发现有n个商品第i个商品价值vi元重wi千克他希望拿走的价值尽量高，
# 但他的背包最多只能容纳W千克东西他应该拿走哪些商品。
# 0-1背包：对于一个商品，小偷要么把他完整拿走，要么留下，不能只拿走一部分，
# 或者吧一个商品拿走多次

# 分数背包：对于一个商品，小偷可以拿走其中任意一部分（商品为金砂）
# ep： 商品1 v1=60 w1=10 商品2 v2=100 w2=20 商品3 v3=120 w3=30 背包容量W=50

# 背包问题使用分数背包计算

# goods=[(60,10),(100,20),(120,30)]
# goods.sort(key=lambda x:x[0]/x[1],reverse=True)#对goods排序
#
# def fractional_backpack(goods,w):
#     m=[0 for _ in range(len(goods))]
#     total_v=0#计算价值
#     for i,(prize,weight) in enumerate(goods):
#         if w >=weight:
#             m[i]=1
#             total_v+=prize
#             w-=weight
#         else:
#             m[i]=w/weight
#             total_v+=m[i]*prize
#             w=0
#             break
#     return m,total_v
#
# print(fractional_backpack(goods,50))

# 有n个非负整数，将其按字符串拼接的方式拼接为一个整数。如何拼接可以使得得到的整数最大
# 例：32，94，128，1286，6，71可以拼接除的最大整数为
# 94716321286128


# from functools import cmp_to_key
#
# li =[32,94,128,1286,6,71]
#
#
# def xy_cmp(x,y):
#     if x+y<y+x:
#         return 1
#     elif x+y>y+x:
#         return -1
#     else:
#         return 0
#
#
# def number_join(li):
#     li=list(map(str,li))
#
#     li.sort(key=cmp_to_key(xy_cmp))
#     return "".join(li)
#
# print(number_join(li))


# 85
# 活动选择问题
# 假设有n个获得这些活动要占用同一片场地，而场地在某时刻智能供一个活动使用。
# 每个活动都有一个开始时间Si和结束时间fi（题中以整数表示，
# 表示活动在[si,fi)区间占用场地
#
# 问 安排哪些活动能够使该场地举办的活动的个数最多
#
# i  1    2   3   4   5   6   7   8   9   10  11
# si 1    3   0   5   3   5   6   8   8   2   12
# fi 4    5   6   7   9   9   10  11  12  14  16

# activates=[(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),
#            (8,12),(2,14),(12,16)]
#
# activates.sort(key=lambda x:x[1])
#
# def activity_selection(a):
#     res=[a[0]]
#     for i in range(1,len(a)):
#         if a[i][0] >= res[-1][1]:
#             res.append(a[i])
#     return res
#
# print(activity_selection(activates))


# 87动态规划DP
# 最优子结构

# 从斐波那契数列看动态规划
# 斐波那契数列 F n=F n-1 + F n-2
# 练习 使用递归和非递归的方法来求解斐波那契数列的第项
# 递归方式
# def fibnacci(n):
#     if n==1 or n == 2:
#         return 1
#     else:
#         return fibnacci(n-1)+fibnacci(n+1)
#
# #非递归
# def fibnacci_no_recurision(n):
#     f = [0,1,1]
#     if n >2:
#         for i in range(n-2):
#             num = f[-1]+f[-2]
#             f.append(num)
#     return f[n]
#
#
# fibnacci_no_recurision(19)

# 88
# 钢条切割问题
# 某公司出售钢条，出售价格与钢条长度之间的关系如下表：
# 长度 i    1    2   3   4   5   6   7   8   9   10
# 价格pi    1    5   8   9   10  17  17  20  24  30
#
# 问题 现有一段长度为n的钢条和上面的价格表，求切割钢条方案，是得总收益最大。

# 递推式
# 设长度为n的钢条切割后最优收益值为rn，可以得出递推式：
# rn=max(pn,r1+rn-1,r2+rn-2+...+rn-1+r1)
# 第一个参数pn表示不切割
# 其他 n-1个参数分别表示另外n-1种不同切割方案，对方案i-1,2...n-1
#     将钢条切割为长度为1和n-1两段
#     方案i的收益为切割两段的最优收益之和
# 考察所有的i选择其中收益最大的方案

# 最优子结构
# 可以将求解规模为n的原问题，划分为规模更小的子问题，完成一次切割后，
# 可以将长生的两段钢条看成两个独立的钢条切割问题
#
# 组合两个子问题的最优解并在所有可能的  两段切割方案中选取组合收益最大的
# 构成员原问题的最优解
#
# 钢条切割满足最优子结构 问题的最优解由相关子问题的最优解组合而成，
# 这些子问题可以独立求解。

# 更简单的递归求解方法
# 从钢条的左边切割下长度为i的一段，只对右边剩下的一段继续进行切割，左边的不再切割
# 递推式简化为rn=max（pi+rn-1)
# max 1<=i<=n
# 不做切割的方案就可以描述为：左边一段长度为n收益为pn剩余一段长度为0，收益为r0=0

# import time
#
#
# def cal_time(func):
#     def wrapper(*args, **kwargs):
#         t1 = time.time()
#         result = func(*args, **kwargs)
#         t2 = time.time()
#         print("%s running time : %s secs." % (func.__name__, t2 - t1))
#
#     return wrapper
#
#
# p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
#
#
# def cut_rod_recurision_1(p, n):
#     if n == 0:
#         return 0
#     else:
#         res = p[n]
#         for i in range(1, n):
#             res = max(res, cut_rod_recurision_1(p, i) + cut_rod_recurision_1(p, n - i))
#             # rn = max(pn, r1 + rn - 1, r2 + rn - 2 + ... + rn - 1 + r1)
#         return res
#
#
# def cut_rod_recurision_2(p, n):
#     if n == 0:
#         return 0
#     else:
#         res = 0
#         for i in range(1, n + 1):
#             res = max(res, p[i] + cut_rod_recurision_2(p, n - i))
#             # 递推式简化为rn = max（pi + rn - 1)
#         return res
#
#
# @cal_time
# def c1(p, n):
#     return cut_rod_recurision_1(p, n)
#
#
# @cal_time
# def c2(p, n):
#     return cut_rod_recurision_2(p, n)

# print(c2(p,9))
# 由于函数内部存在递归 无法直接调用装饰器 所以定义新函数


# 钢条切割问题  自顶向下递归实现 cut_rod_recurision_2
#自顶向下递归时间复杂度为O(2**n)

# 钢条切割 动态规划求解
# 递归算法由于重复计算相同子问题导致效率降低

# 动态规划思想：
#  每个子问题只求解一次 ，保存求解结果
# 之后需要此问题，查找保存的结果

#91
#动态规划 时间复杂度 O(N***2) 2的100次方和100的2次方
# def cut_rod_dp(p,n):
#     r=[0]
#     for i in range(1,n+1):
#         res=0
#         for j in range(1,i+1):
#             res=max(res,p[j]+r[i-j])
#         r.append(res)
#     return r[n]
#
# #print(cut_rod_dp(p,9))
#
# def cut_rod_extend(p,n):
#     r=[0]
#     s=[0]
#     for i in range(1,n+1):
#         res_r=0 #价格最大值
#         res_s=0 #价格最大值对应方案的左边不切割部分的长度
#         for j in range(1,i+1):
#             if p[j] + r[i-j]>res_r:
#                 res_r=p[j]+r[i-j]
#                 res_s=j
#         r.append(res_r)
#         s.append(res_s)
#     return r[n],s
#
# def cut_rod_solution(p,n):
#     r,s=cut_rod_extend(p,n)
#     ans=[]
#     while n>0:
#         ans.append(s[n])
#         n -=s[n]
#     return ans
# s=cut_rod_solution(p,9)
#
# print(s)


#91
# 动态规划问题关键：
# ！！！
# 什么问题可以使用动态规划
# 最优子结构
# 原问题的最优解中涉及多少个子问题
# 在确定最优解使用哪些子问题时，需要考虑多少种选择
# 重叠子问题





# -------------------------------------------------------------------------------
# 补充
# random.shuffle(list)可把列表变成乱序
# 修改递归的最大深度 import sys
# sys.setrecursionlimit(n) 可把最大递归深度修改到n
# 函数注释 三个双引号后回车
# 如果输出是换行的单个的可以直接输出不用存列表再拆包


# #前缀和测试
# n=[]
# N,m=map(int,input().split())#m操作次数 n数组长度
# n[0:]=map(int,input().split())
# while m>0:
#     l,r=map(int,input().split())
#     m-=1
# all_num=sum(n[0:r])
# all_num2=sum(n[0:l-1])
# print(all_num-all_num2)
# 当给定长度为n序列a时 a1,a2,...an则
# 前n项和sum[a]=a1+a2+a3+...+an=sum[0:n]+an
# 解释：前n 项和就等于前n-1项和加第n项
# 切片语法左闭右开。


# -------------------------------


# 简单前缀和
# a=[1,2,5,8,9,6,4,7]
# A=[0]*len(a)
# for i in range(len(a)):
#     if i >=1:
#         A[i]=A[i-1]+a[i]
#     else:
#         A[0]=a[i]
# print(A)

# 关于前缀和和差分总结
# 其实前缀和没什么说的 求和相加 但是这里要注意
# 求出的是前缀和数组和差分数组
# ep：a=[1,2,3,5,7]
# 差分数组[1,1,1,2,2]
# 前缀和数组[1,2,3,5,7]
# 差分和前缀和互为逆运算

# 注意！！！
# 像跨零杯LED灯 相当于区间是1-每个m
# 如果m==n 相当于 对每个灯都操作一次 这是对差分数组的操作 只要对第一个加1就行
# -----------------------------------------------------


# python二维列表排序

# 假设a为二维列表 每个列表存贮了排名 名字 年龄 ep：a=[[3,"lisi",18]]
# 如果要按排名排序则代码为
# a.sort(key=lambda x:x[0])
# 或者
# sorted(a.key=(lambda x:x[0])
# 另外 sort直接对原有列表排序 原列表被改变 而sorted直接返回一个排好序的新列表
